package dipl.algorithm.math.fp.geometry;

import dipl.algorithm.math.fp.geometry.op.Point2dSetOps;
import dipl.algorithm.math.fp.primitive.Point2df;
import dipl.algorithm.math.fp.primitive.op.Point2dOps;

/**
 * Represents the convex hull of a given 2d point set.
 * The convex hull is represented by a convex polygon.
 * The vertices of the polygon are ordered clockwise.
 *
 * Additionally the class stores the indices of hull-vertices which are the first and last point
 * of the original pointset. (if they are contained in hull vertices)
 */
public class ConvexHull2d {

	//
	// CONSTRUCTOR METHODS
	//

	public ConvexHull2d() {
		this.pointset = null;
		this.vertices = null;
		this.pointsetFirstIndex = -1;
		this.pointsetLastIndex = -1;
	}

	public ConvexHull2d( Point2df[] pointset ) {
		this.pointset = pointset;
		this.vertices = null;
		this.pointsetFirstIndex = -1;
		this.pointsetLastIndex = -1;
		if( this.pointset != null && this.pointset.length > 0 )
			ReconstructHull();
	}

	/**
	 * 
	 * @param other
	 */
	public ConvexHull2d( ConvexHull2d other ) {
		this.pointset = other.pointset;
		this.vertices = other.vertices;
		this.pointsetFirstIndex = other.pointsetFirstIndex;
		this.pointsetLastIndex = other.pointsetLastIndex;
	}

	//
	// PUBLIC METHODS
	//

	/**
	 * Constructs hull from point set.
	 * @param fpMath
	 */
	public void ReconstructHull() {
		int n = pointset.length; // number of points

		// special cases
		if( n == 1 ) {
			vertices = new Point2df[1];
			vertices[0] = pointset[0];
			return;
		}

		int i; // index

		Point2df[] temp = new Point2df[n]; // temporary copy of pointset (for sorting etc)
		for( i = 0; i < n; i++ )
			temp[i] = pointset[i];

		// sort points lexicographically first
		Point2dSetOps.SortPointsLexicographically( temp );

		Point2df[] hull = new Point2df[2*n]; // contains hull calculated so far
		int index; // highest index in hull so far

		// construct upper hull

		hull[0] = temp[0];
		hull[1] = temp[1];
		index = 1;
		for( i = 2; i < n; i++ ) {
			index++;
			hull[index] = temp[i];
			while( index > 1 && !Point2dOps.MakeRightTurn( hull[index-2], hull[index-1], hull[index] ) ) {
				hull[index-1] = hull[index];
				index--;
			}
		}

		int upperHullSize = index+1; // hull size at this moment

		// construct lower hull
		index++;
		hull[index] = temp[n-2];
		for( i = n-3; i >= 0; i-- ) {
			index++;
			hull[index] = temp[i];
			while( index > upperHullSize && !Point2dOps.MakeRightTurn( hull[index-2], hull[index-1], hull[index] ) ) {
				hull[index-1] = hull[index];
				index--;
			}
		}
		index--; // last point is twice in list (first and last)

		// fill hullset with hull points
		vertices = new Point2df[index+1];
		for( i = 0; i <= index; i++ ) {
			if( hull[i] == pointset[0] ) {
				pointsetFirstIndex = i;
			}
			if( hull[i] == pointset[n-1] ) {
				pointsetLastIndex = i;
			}
			vertices[i] = hull[i];
		}
	}

	//
	// PROPERTIES
	//

	/**
	 * Gets index of hull point corresponding to pointset's point with index 0
	 * If that point is not contained in hull points then -1 is returned.
	 * @return
	 */
	public int FirstPointsetIndex() {
		return pointsetFirstIndex;
	}

	/**
	 * Gets index of hull point corresponding to highest pointset's point index
	 * If that point is not contained in hull points then -1 is returned.
	 * @return
	 */
	public int LastPointsetIndex() {
		return pointsetLastIndex; 
	}

	/**
	 * Gets convex hull's original pointset.
	 * @return
	 */
	public Point2df[] Pointset() {
		return pointset;
	}

	/**
	 * Gets convex hull's vertices.
	 * @return
	 */
	public Point2df[] Vertices() {
		return vertices; 
	}

	public void SetFirstPointsetIndex( int index ) {
		this.pointsetFirstIndex = index;
	}

	public void SetLastPointsetIndex( int index ) {
		pointsetLastIndex = index;
	}

	public void SetVertices( Point2df[] vertices ) {
		this.vertices = vertices;
	}

	//
	// MEMBERS
	//

	/**
	 * original pointset
	 */
	protected Point2df[] pointset;

	/**
	 * points of onvex hull ordered clockwise
	 */
	protected Point2df[] vertices;

	/**
	 * index of point in convex hull corresponding to first point in original point set
	 */
	protected int pointsetFirstIndex;

	/**
	 * index of point in convex hull corresponding to last point in oringal point set
	 */
	protected int pointsetLastIndex;
}
